<html>
 <head>
  <meta charset="UTF-8">
 </head>
 <body>
  <h1 data-lake-id="Wp3CR" id="Wp3CR"><span data-lake-id="u328b98e7" id="u328b98e7">典型回答</span></h1>
  <p data-lake-id="u5faf7053" id="u5faf7053"><span data-lake-id="u5d17458c" id="u5d17458c">从定义上来说，所谓的树，就是由节点和边组成，且不存在环的一种数据结构。</span></p>
  <p data-lake-id="u0e0c5cf3" id="u0e0c5cf3"><span data-lake-id="u6c26ff2f" id="u6c26ff2f">从实现上来讲，树一般通过链表来实现。</span></p>
  <p data-lake-id="uf1ee0706" id="uf1ee0706"><span data-lake-id="u3ed4e8a7" id="u3ed4e8a7">从结构上分，树可分为二叉树和多叉树。一般我们在写算法的时候，使用二叉树和字典树比较多。</span></p>
  <p data-lake-id="u1053a5f2" id="u1053a5f2"><span data-lake-id="u3fb4b4e1" id="u3fb4b4e1">​</span><br></p>
  <p data-lake-id="u229fa508" id="u229fa508"><span data-lake-id="u5911c24f" id="u5911c24f">除此之外，</span></p>
  <ol list="u9c41ae73">
   <li fid="u8460c9de" data-lake-id="uf9157ff6" id="uf9157ff6"><span data-lake-id="u988aa96b" id="u988aa96b">B*树一般用于数据库的索引，特点是由多个子树，高度很低，可以减少磁盘IO；</span></li>
   <li fid="u8460c9de" data-lake-id="ud34ca2bf" id="ud34ca2bf"><span data-lake-id="ua85511ce" id="ua85511ce">霍夫曼树一般通过哈夫曼编码做数据的无损压缩；（这个是大学数据结构的必修内容，但是面试一般不考）</span></li>
   <li fid="u8460c9de" data-lake-id="uf8e0a3e4" id="uf8e0a3e4"><span data-lake-id="uff11548b" id="uff11548b">红黑树和平衡二叉树因为是有序的，所以经常用于二分查找，红黑树相对于平衡二叉树的优点是，不要求树完全平衡，这就会降低数据更新时候的时间复杂度。Java中的HashMap就会通过红黑树来进行查找；</span></li>
   <li fid="u8460c9de" data-lake-id="ucc596d2a" id="ucc596d2a"><span data-lake-id="u78413f9d" id="u78413f9d">字典树一般是针对一组字符串进行维护的数据结构，它可以将共同前缀的字符串进行优化，节省存储空间，同时可以快速查询某个字符串是否出现。（在LeetCode Hard中比较常见）</span></li>
  </ol>
  <p data-lake-id="u620bf0d0" id="u620bf0d0"><span data-lake-id="u72522898" id="u72522898">树的分类如下所示：</span></p>
  <p data-lake-id="ueac083c1" id="ueac083c1"><img src="https://cdn.nlark.com/yuque/0/2023/png/719664/1676790533990-dbdc9fc3-6a18-4c42-a2ff-da17aef3db29.png?x-oss-process=image%2Fwatermark%2Ctype_d3F5LW1pY3JvaGVp%2Csize_34%2Ctext_SmF2YSA4IEd1IFA%3D%2Ccolor_FFFFFF%2Cshadow_50%2Ct_80%2Cg_se%2Cx_10%2Cy_10"></p>
  <blockquote data-lake-id="ue577d600" id="ue577d600">
   <ul list="u0a26ac11">
    <li fid="ue20b63c1" data-lake-id="uebadca09" id="uebadca09"><span data-lake-id="u46e9be84" id="u46e9be84">注意：上图中的字典树就是Tire树，</span></li>
   </ul>
  </blockquote>
  <h1 data-lake-id="s25mQ" id="s25mQ"><span data-lake-id="ub86ece2b" id="ub86ece2b">知识扩展</span></h1>
  <h2 data-lake-id="dA5Zy" id="dA5Zy"><span data-lake-id="u02708808" id="u02708808">二叉查找树的演变和区别？</span></h2>
  <p data-lake-id="u9a2ee3e2" id="u9a2ee3e2"><span data-lake-id="ub61684f6" id="ub61684f6">参考该文章中第二条：</span><a href="https://www.yuque.com/hollis666/vhr2ge/zx609g" data-lake-id="uf1e312df" id="uf1e312df"><span data-lake-id="u45c23195" id="u45c23195">为什么是红黑树</span></a></p>
  <h2 data-lake-id="ula6r" id="ula6r"><span data-lake-id="uaaf04fc5" id="uaaf04fc5">什么是字典树？</span></h2>
 </body>
</html>